The ultimate purpose of a communication system is to transmit information from an information source to a destination over a communication channel. A communication channel is any medium over which information can be transmitted. In many types of communication channels, such as radio communication channels, noise is inherent. The inherent noise causes errors to occur in the information transmitted over the communication channel. In order to combat the noisy channel, and hence reduce bit errors, digital cellular radio systems typically employ both error-detecting and error-correcting codes. These error control techniques introduce controlled redundancy into the information transmitted over the communication channel which can be used at the destination to detect and possibly correct errors in the channel corrupted signal.
One well-known technique for error-correction uses convolutional codes as described by Andrew Viterbi and Jim Omura in their publication Principles of Digital Communication and Coding published by McGraw-Hill, Inc., New York, N.Y. 1979. With convolutional encoding, information bits are encoded and decoded in such a way as to estimate bits that were corrupted in transmission. Convolutional codes are typically described by the rate of the code, its constraint length, and the parity equations.
In a convolutional code having a rate of k/n, n output bits are produced for each set of k information bits. During each coding interval, k information bits are shifted into the shift register and n bits (where n&gt;k) are produced at the output of the shift register. The redundancy bits are combinations (linear algebraic functions) of the contents of the shift register and the most recent input bit, with the specific combinatorial function depending on the convolutional code implemented. The state of the encoder at a given time is defined as the contents of the shift register. In practice, such convolutional codes may be divided into two classes: recursive and non-recursive codes. The implementation of non-recursive codes typically involves the incorporation of a feed-forward type shift register, while recursive codes generally require an encoder with a feedback circuit.
Tail bits and tail-biting are commonly used methods to terminate the trellises or coding paths, of convolutional codes for short block lengths. When tail-bits are used, the encoder is forced to a known state at the end of the block. Tail-biting constrains the encoder to begin and end at the same state, which necessarily depends on the data sequence being transmitted.
For the feed-forward or non-recursive case, it is relatively easy to find the initial state of the encoder which satisfies the tail-biting requirement. In practice, the feed-forward shift register is simply initialized with the last m bits of the input sequence, where m is the memory of the code. However, in the case of recursive codes, it is not as easy to find the initial state of the encoder which satisfies the tail-biting requirement. This is primarily the result of the feedback nature of the recursive encoder.
Therefore, there is and continues to be a need for a practical and efficient technique for determining the initial or starting state of a recursive convolutional feedback encoder to enable the use of tail-biting codes.